package leetcode.sword;

import java.util.ArrayList;

class MedianFinder {

    //想法1：维护一个有序数组,小-》大
    //addNum就是插入，复杂度n
    //findMedia随机寻址，复杂度1
    ArrayList nums;
    int size;

    public static void main(String[] args) {
        MedianFinder mf = new MedianFinder();
        mf.addNum(12);
        System.out.println(mf.findMedian());
        mf.addNum(10);
        System.out.println(mf.findMedian());
        mf.addNum(13);
        System.out.println(mf.findMedian());
        mf.addNum(11);
        System.out.println(mf.findMedian());
    }

    public MedianFinder() {
        nums = new ArrayList();
        size = 0;
    }

    public void addNum(int num) {
        int start = 0, end = size-1, mid, midd;
        while(start<end){
            mid = (start+end)/2;
            midd = (int)nums.get(mid);
            if(num==midd){
                start = mid;
                break;
            }else if(num>midd){
                start = mid+1;
            }else{// num<nums.get(mid)
                end = mid-1;
            }
        }
        if(size>0&&num>(int)nums.get(start)) start +=1;
        nums.add(start,num);
        size++;
    }

    public double findMedian() {
        // if(size==0) return null;
        if(size%2==0){//偶数个
            return ((int)nums.get(size/2) + (int)nums.get(size/2-1))/2.0;
        }else{
            return (int)nums.get(size/2);
        }
    }


    //想法2：维护一个搜索二叉树，
    //addNUm就是增加节点，复杂度logn
    //findMedian就是中序遍历到NUms/2个节点，复杂度logn
    /** initialize your data structure here. */
    // public java.sword.MedianFinder() {
    // }

    // public void addNum(int num) {
    // }

    // public double findMedian() {
    // }



}

/**
 * Your java.sword.MedianFinder object will be instantiated and called as such:
 * java.sword.MedianFinder obj = new java.sword.MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */